// Copyright (c) 2014, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// This translation unit generates microdumps into the console (logcat on
// Android). See crbug.com/410294 for more info and design docs.

#include "client/linux/microdump_writer/microdump_writer.h"

#include <limits>

#include <sys/utsname.h>

#include "client/linux/dump_writer_common/thread_info.h"
#include "client/linux/dump_writer_common/ucontext_reader.h"
#include "client/linux/handler/exception_handler.h"
#include "client/linux/handler/microdump_extra_info.h"
#include "client/linux/log/log.h"
#include "client/linux/minidump_writer/linux_ptrace_dumper.h"
#include "common/linux/file_id.h"
#include "common/linux/linux_libc_support.h"
#include "common/memory_allocator.h"

namespace {

    using google_breakpad::auto_wasteful_vector;
    using google_breakpad::ExceptionHandler;
    using google_breakpad::kDefaultBuildIdSize;
    using google_breakpad::LinuxDumper;
    using google_breakpad::LinuxPtraceDumper;
    using google_breakpad::MappingInfo;
    using google_breakpad::MappingList;
    using google_breakpad::MicrodumpExtraInfo;
    using google_breakpad::RawContextCPU;
    using google_breakpad::ThreadInfo;
    using google_breakpad::UContextReader;

    const size_t kLineBufferSize = 2048;

#if !defined(__LP64__)
// The following are only used by DumpFreeSpace, so need to be compiled
// in conditionally in the same way.

    template<typename Dst, typename Src>
    Dst saturated_cast(Src src) {
        if (src >= std::numeric_limits<Dst>::max())
            return std::numeric_limits<Dst>::max();
        if (src <= std::numeric_limits<Dst>::min())
            return std::numeric_limits<Dst>::min();
        return static_cast<Dst>(src);
    }

    int Log2Floor(uint64_t n) {
        // Copied from chromium src/base/bits.h
        if (n == 0)
            return -1;
        int log = 0;
        uint64_t value = n;
        for (int i = 5; i >= 0; --i) {
            int shift = (1 << i);
            uint64_t x = value >> shift;
            if (x != 0) {
                value = x;
                log += shift;
            }
        }
        assert(value == 1u);
        return log;
    }

    bool MappingsAreAdjacent(const MappingInfo &a, const MappingInfo &b) {
        // Because of load biasing, we can end up with a situation where two
        // mappings actually overlap. So we will define adjacency to also include a
        // b start address that lies within a's address range (including starting
        // immediately after a).
        // Because load biasing only ever moves the start address backwards, the end
        // address should still increase.
        return a.start_addr <= b.start_addr && a.start_addr + a.size >= b.start_addr;
    }

    bool MappingLessThan(const MappingInfo *a, const MappingInfo *b) {
        // Return true if mapping a is before mapping b.
        // For the same reason (load biasing) we compare end addresses, which - unlike
        // start addresses - will not have been modified.
        return a->start_addr + a->size < b->start_addr + b->size;
    }

    size_t NextOrderedMapping(
            const google_breakpad::wasteful_vector<MappingInfo *> &mappings,
            size_t curr) {
        // Find the mapping that directly follows mappings[curr].
        // If no such mapping exists, return |invalid| to indicate this.
        const size_t invalid = std::numeric_limits<size_t>::max();
        size_t best = invalid;
        for (size_t next = 0; next < mappings.size(); ++next) {
            if (MappingLessThan(mappings[curr], mappings[next]) &&
                (best == invalid || MappingLessThan(mappings[next], mappings[best]))) {
                best = next;
            }
        }
        return best;
    }

#endif  // !__LP64__

    class MicrodumpWriter {
    public:
        MicrodumpWriter(const ExceptionHandler::CrashContext *context,
                        const MappingList &mappings,
                        bool skip_dump_if_principal_mapping_not_referenced,
                        uintptr_t address_within_principal_mapping,
                        bool sanitize_stack,
                        const MicrodumpExtraInfo &microdump_extra_info,
                        LinuxDumper *dumper)
                : ucontext_(context ? &context->context : NULL),
#if !defined(__ARM_EABI__) && !defined(__mips__)
                  float_state_(context ? &context->float_state : NULL),
#endif
                  dumper_(dumper),
                  mapping_list_(mappings),
                  skip_dump_if_principal_mapping_not_referenced_(
                          skip_dump_if_principal_mapping_not_referenced),
                  address_within_principal_mapping_(address_within_principal_mapping),
                  sanitize_stack_(sanitize_stack),
                  microdump_extra_info_(microdump_extra_info),
                  log_line_(NULL),
                  stack_copy_(NULL),
                  stack_len_(0),
                  stack_lower_bound_(0),
                  stack_pointer_(0) {
            log_line_ = reinterpret_cast<char *>(Alloc(kLineBufferSize));
            if (log_line_)
                log_line_[0] = '\0';  // Clear out the log line buffer.
        }

        ~MicrodumpWriter() { dumper_->ThreadsResume(); }

        bool Init() {
            // In the exceptional case where the system was out of memory and there
            // wasn't even room to allocate the line buffer, bail out. There is nothing
            // useful we can possibly achieve without the ability to Log. At least let's
            // try to not crash.
            if (!dumper_->Init() || !log_line_)
                return false;
            return dumper_->ThreadsSuspend() && dumper_->LateInit();
        }

        void Dump() {
            CaptureResult stack_capture_result = CaptureCrashingThreadStack(-1);
            if (stack_capture_result == CAPTURE_UNINTERESTING) {
                LogLine("Microdump skipped (uninteresting)");
                return;
            }

            LogLine("-----BEGIN BREAKPAD MICRODUMP-----");
            DumpProductInformation();
            DumpOSInformation();
            DumpProcessType();
            DumpCrashReason();
            DumpGPUInformation();
#if !defined(__LP64__)
            DumpFreeSpace();
#endif
            if (stack_capture_result == CAPTURE_OK)
                DumpThreadStack();
            DumpCPUState();
            DumpMappings();
            LogLine("-----END BREAKPAD MICRODUMP-----");
        }

    private:
        enum CaptureResult {
            CAPTURE_OK, CAPTURE_FAILED, CAPTURE_UNINTERESTING
        };

        // Writes one line to the system log.
        void LogLine(const char *msg) {
#if defined(__ANDROID__)
            logger::writeToCrashLog(msg);
#else
            logger::write(msg, my_strlen(msg));
            logger::write("\n", 1);
#endif
        }

        // Stages the given string in the current line buffer.
        void LogAppend(const char *str) {
            my_strlcat(log_line_, str, kLineBufferSize);
        }

        // As above (required to take precedence over template specialization below).
        void LogAppend(char *str) {
            LogAppend(const_cast<const char *>(str));
        }

        // Stages the hex repr. of the given int type in the current line buffer.
        template<typename T>
        void LogAppend(T value) {
            // Make enough room to hex encode the largest int type + NUL.
            static const char HEX[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                                       'A', 'B', 'C', 'D', 'E', 'F'};
            char hexstr[sizeof(T) * 2 + 1];
            for (int i = sizeof(T) * 2 - 1; i >= 0; --i, value >>= 4)
                hexstr[i] = HEX[static_cast<uint8_t>(value) & 0x0F];
            hexstr[sizeof(T) * 2] = '\0';
            LogAppend(hexstr);
        }

        // Stages the buffer content hex-encoded in the current line buffer.
        void LogAppend(const void *buf, size_t length) {
            const uint8_t *ptr = reinterpret_cast<const uint8_t *>(buf);
            for (size_t i = 0; i < length; ++i, ++ptr)
                LogAppend(*ptr);
        }

        // Writes out the current line buffer on the system log.
        void LogCommitLine() {
            LogLine(log_line_);
            log_line_[0] = 0;
        }

        CaptureResult CaptureCrashingThreadStack(int max_stack_len) {
            stack_pointer_ = UContextReader::GetStackPointer(ucontext_);

            if (!dumper_->GetStackInfo(reinterpret_cast<const void **>(&stack_lower_bound_),
                                       &stack_len_, stack_pointer_)) {
                return CAPTURE_FAILED;
            }

            if (max_stack_len >= 0 &&
                stack_len_ > static_cast<size_t>(max_stack_len)) {
                stack_len_ = max_stack_len;
            }

            stack_copy_ = reinterpret_cast<uint8_t *>(Alloc(stack_len_));
            dumper_->CopyFromProcess(stack_copy_, dumper_->crash_thread(),
                                     reinterpret_cast<const void *>(stack_lower_bound_),
                                     stack_len_);

            if (!skip_dump_if_principal_mapping_not_referenced_) return CAPTURE_OK;

            const MappingInfo *principal_mapping =
                    dumper_->FindMappingNoBias(address_within_principal_mapping_);
            if (!principal_mapping) return CAPTURE_UNINTERESTING;

            uintptr_t low_addr = principal_mapping->system_mapping_info.start_addr;
            uintptr_t high_addr = principal_mapping->system_mapping_info.end_addr;
            uintptr_t pc = UContextReader::GetInstructionPointer(ucontext_);
            if (low_addr <= pc && pc <= high_addr) return CAPTURE_OK;

            if (dumper_->StackHasPointerToMapping(stack_copy_, stack_len_,
                                                  stack_pointer_ - stack_lower_bound_,
                                                  *principal_mapping)) {
                return CAPTURE_OK;
            }
            return CAPTURE_UNINTERESTING;
        }

        void DumpProductInformation() {
            LogAppend("V ");
            if (microdump_extra_info_.product_info) {
                LogAppend(microdump_extra_info_.product_info);
            } else {
                LogAppend("UNKNOWN:0.0.0.0");
            }
            LogCommitLine();
        }

        void DumpProcessType() {
            LogAppend("P ");
            if (microdump_extra_info_.process_type) {
                LogAppend(microdump_extra_info_.process_type);
            } else {
                LogAppend("UNKNOWN");
            }
            LogCommitLine();
        }

        void DumpCrashReason() {
            LogAppend("R ");
            LogAppend(dumper_->crash_signal());
            LogAppend(" ");
            LogAppend(dumper_->GetCrashSignalString());
            LogAppend(" ");
            LogAppend(dumper_->crash_signal_code());
            LogAppend(" ");
            LogAppend(dumper_->crash_address());
            LogCommitLine();
        }

        void DumpOSInformation() {
            const uint8_t n_cpus = static_cast<uint8_t>(sysconf(_SC_NPROCESSORS_CONF));

#if defined(__ANDROID__)
            const char kOSId[] = "A";
#else
            const char kOSId[] = "L";
#endif

// Dump the runtime architecture. On multiarch devices it might not match the
// hw architecture (the one returned by uname()), for instance in the case of
// a 32-bit app running on a aarch64 device.
#if defined(__aarch64__)
            const char kArch[] = "arm64";
#elif defined(__ARMEL__)
            const char kArch[] = "arm";
#elif defined(__x86_64__)
            const char kArch[] = "x86_64";
#elif defined(__i386__)
            const char kArch[] = "x86";
#elif defined(__mips__)
# if _MIPS_SIM == _ABIO32
            const char kArch[] = "mips";
# elif _MIPS_SIM == _ABI64
            const char kArch[] = "mips64";
# else
#  error "This mips ABI is currently not supported (n32)"
#endif
#else
#error "This code has not been ported to your platform yet"
#endif

            LogAppend("O ");
            LogAppend(kOSId);
            LogAppend(" ");
            LogAppend(kArch);
            LogAppend(" ");
            LogAppend(n_cpus);
            LogAppend(" ");

            // Dump the HW architecture (e.g., armv7l, aarch64).
            struct utsname uts;
            const bool has_uts_info = (uname(&uts) == 0);
            const char *hwArch = has_uts_info ? uts.machine : "unknown_hw_arch";
            LogAppend(hwArch);
            LogAppend(" ");

            // If the client has attached a build fingerprint to the MinidumpDescriptor
            // use that one. Otherwise try to get some basic info from uname().
            if (microdump_extra_info_.build_fingerprint) {
                LogAppend(microdump_extra_info_.build_fingerprint);
            } else if (has_uts_info) {
                LogAppend(uts.release);
                LogAppend(" ");
                LogAppend(uts.version);
            } else {
                LogAppend("no build fingerprint available");
            }
            LogCommitLine();
        }

        void DumpGPUInformation() {
            LogAppend("G ");
            if (microdump_extra_info_.gpu_fingerprint) {
                LogAppend(microdump_extra_info_.gpu_fingerprint);
            } else {
                LogAppend("UNKNOWN");
            }
            LogCommitLine();
        }

        void DumpThreadStack() {
            if (sanitize_stack_) {
                dumper_->SanitizeStackCopy(stack_copy_, stack_len_, stack_pointer_,
                                           stack_pointer_ - stack_lower_bound_);
            }

            LogAppend("S 0 ");
            LogAppend(stack_pointer_);
            LogAppend(" ");
            LogAppend(stack_lower_bound_);
            LogAppend(" ");
            LogAppend(stack_len_);
            LogCommitLine();

            const size_t STACK_DUMP_CHUNK_SIZE = 384;
            for (size_t stack_off = 0; stack_off < stack_len_;
                 stack_off += STACK_DUMP_CHUNK_SIZE) {
                LogAppend("S ");
                LogAppend(stack_lower_bound_ + stack_off);
                LogAppend(" ");
                LogAppend(stack_copy_ + stack_off,
                          std::min(STACK_DUMP_CHUNK_SIZE, stack_len_ - stack_off));
                LogCommitLine();
            }
        }

        void DumpCPUState() {
            RawContextCPU cpu;
            my_memset(&cpu, 0, sizeof(RawContextCPU));
#if !defined(__ARM_EABI__) && !defined(__mips__)
            UContextReader::FillCPUContext(&cpu, ucontext_, float_state_);
#else
            UContextReader::FillCPUContext(&cpu, ucontext_);
#endif
            LogAppend("C ");
            LogAppend(&cpu, sizeof(cpu));
            LogCommitLine();
        }

        // If there is caller-provided information about this mapping
        // in the mapping_list_ list, return true. Otherwise, return false.
        bool HaveMappingInfo(const MappingInfo &mapping) {
            for (MappingList::const_iterator iter = mapping_list_.begin();
                 iter != mapping_list_.end();
                 ++iter) {
                // Ignore any mappings that are wholly contained within
                // mappings in the mapping_info_ list.
                if (mapping.start_addr >= iter->first.start_addr &&
                    (mapping.start_addr + mapping.size) <=
                    (iter->first.start_addr + iter->first.size)) {
                    return true;
                }
            }
            return false;
        }

        // Dump information about the provided |mapping|. If |identifier| is non-NULL,
        // use it instead of calculating a file ID from the mapping.
        void DumpModule(const MappingInfo &mapping,
                        bool member,
                        unsigned int mapping_id,
                        const uint8_t *identifier) {

            auto_wasteful_vector<uint8_t, kDefaultBuildIdSize> identifier_bytes(
                    dumper_->allocator());

            if (identifier) {
                // GUID was provided by caller.
                identifier_bytes.insert(identifier_bytes.end(),
                                        identifier,
                                        identifier + sizeof(MDGUID));
            } else {
                dumper_->ElfFileIdentifierForMapping(
                        mapping,
                        member,
                        mapping_id,
                        identifier_bytes);
            }

            // Copy as many bytes of |identifier| as will fit into a MDGUID
            MDGUID module_identifier = {0};
            memcpy(&module_identifier, &identifier_bytes[0],
                   std::min(sizeof(MDGUID), identifier_bytes.size()));

            char file_name[NAME_MAX];
            char file_path[NAME_MAX];
            dumper_->GetMappingEffectiveNameAndPath(
                    mapping, file_path, sizeof(file_path), file_name, sizeof(file_name));

            LogAppend("M ");
            LogAppend(static_cast<uintptr_t>(mapping.start_addr));
            LogAppend(" ");
            LogAppend(mapping.offset);
            LogAppend(" ");
            LogAppend(mapping.size);
            LogAppend(" ");
            LogAppend(module_identifier.data1);
            LogAppend(module_identifier.data2);
            LogAppend(module_identifier.data3);
            LogAppend(module_identifier.data4[0]);
            LogAppend(module_identifier.data4[1]);
            LogAppend(module_identifier.data4[2]);
            LogAppend(module_identifier.data4[3]);
            LogAppend(module_identifier.data4[4]);
            LogAppend(module_identifier.data4[5]);
            LogAppend(module_identifier.data4[6]);
            LogAppend(module_identifier.data4[7]);
            LogAppend("0 ");  // Age is always 0 on Linux.
            LogAppend(file_name);
            LogCommitLine();
        }

#if !defined(__LP64__)

        void DumpFreeSpace() {
            const MappingInfo *stack_mapping = nullptr;
            ThreadInfo info;
            if (dumper_->GetThreadInfoByIndex(dumper_->GetMainThreadIndex(), &info)) {
                stack_mapping = dumper_->FindMappingNoBias(info.stack_pointer);
            }

            const google_breakpad::wasteful_vector<MappingInfo *> &mappings =
                    dumper_->mappings();
            if (mappings.size() == 0) return;

            // This is complicated by the fact that mappings is not in order. It should
            // be mostly in order, however the mapping that contains the entry point for
            // the process is always at the front of the vector.

            static const int HBITS = sizeof(size_t) * 8;
            size_t hole_histogram[HBITS];
            my_memset(hole_histogram, 0, sizeof(hole_histogram));

            // Find the lowest address mapping.
            size_t curr = 0;
            for (size_t i = 1; i < mappings.size(); ++i) {
                if (mappings[i]->start_addr < mappings[curr]->start_addr) curr = i;
            }

            uintptr_t lo_addr = mappings[curr]->start_addr;

            size_t hole_cnt = 0;
            size_t hole_max = 0;
            size_t hole_sum = 0;

            while (true) {
                // Skip to the end of an adjacent run of mappings. This is an optimization
                // for the fact that mappings is mostly sorted.
                while (curr != mappings.size() - 1 &&
                       MappingsAreAdjacent(*mappings[curr], *mappings[curr + 1])) {
                    ++curr;
                }

                if (mappings[curr] == stack_mapping) {
                    // Because we can't determine the top of userspace mappable
                    // memory we treat the start of the process stack as the top
                    // of the allocatable address space. Once we reach
                    // |stack_mapping| we are done scanning for free space regions.
                    break;
                }

                size_t next = NextOrderedMapping(mappings, curr);
                if (next == std::numeric_limits<size_t>::max())
                    break;

                uintptr_t hole_lo = mappings[curr]->start_addr + mappings[curr]->size;
                uintptr_t hole_hi = mappings[next]->start_addr;

                if (hole_hi > hole_lo) {
                    size_t hole_sz = hole_hi - hole_lo;
                    hole_sum += hole_sz;
                    hole_max = std::max(hole_sz, hole_max);
                    ++hole_cnt;
                    ++hole_histogram[Log2Floor(hole_sz)];
                }
                curr = next;
            }

            uintptr_t hi_addr = mappings[curr]->start_addr + mappings[curr]->size;

            LogAppend("H ");
            LogAppend(lo_addr);
            LogAppend(" ");
            LogAppend(hi_addr);
            LogAppend(" ");
            LogAppend(saturated_cast<uint16_t>(hole_cnt));
            LogAppend(" ");
            LogAppend(hole_max);
            LogAppend(" ");
            LogAppend(hole_sum);
            for (unsigned int i = 0; i < HBITS; ++i) {
                if (!hole_histogram[i]) continue;
                LogAppend(" ");
                LogAppend(saturated_cast<uint8_t>(i));
                LogAppend(":");
                LogAppend(saturated_cast<uint8_t>(hole_histogram[i]));
            }
            LogCommitLine();
        }

#endif

        // Write information about the mappings in effect.
        void DumpMappings() {
            // First write all the mappings from the dumper
            for (unsigned i = 0; i < dumper_->mappings().size(); ++i) {
                const MappingInfo &mapping = *dumper_->mappings()[i];
                if (mapping.name[0] == 0 ||  // only want modules with filenames.
                    !mapping.exec ||  // only want executable mappings.
                    mapping.size < 4096 || // too small to get a signature for.
                    HaveMappingInfo(mapping)) {
                    continue;
                }

                DumpModule(mapping, true, i, NULL);
            }
            // Next write all the mappings provided by the caller
            for (MappingList::const_iterator iter = mapping_list_.begin();
                 iter != mapping_list_.end();
                 ++iter) {
                DumpModule(iter->first, false, 0, iter->second);
            }
        }

        void *Alloc(unsigned bytes) { return dumper_->allocator()->Alloc(bytes); }

        const ucontext_t *const ucontext_;
#if !defined(__ARM_EABI__) && !defined(__mips__)
        const google_breakpad::fpstate_t *const float_state_;
#endif
        LinuxDumper *dumper_;
        const MappingList &mapping_list_;
        bool skip_dump_if_principal_mapping_not_referenced_;
        uintptr_t address_within_principal_mapping_;
        bool sanitize_stack_;
        const MicrodumpExtraInfo microdump_extra_info_;
        char *log_line_;

        // The local copy of crashed process stack memory, beginning at
        // |stack_lower_bound_|.
        uint8_t *stack_copy_;

        // The length of crashed process stack copy.
        size_t stack_len_;

        // The address of the page containing the stack pointer in the
        // crashed process. |stack_lower_bound_| <= |stack_pointer_|
        uintptr_t stack_lower_bound_;

        // The stack pointer of the crashed third_party.thread.
        uintptr_t stack_pointer_;
    };
}  // namespace

namespace google_breakpad {

    bool WriteMicrodump(pid_t crashing_process,
                        const void *blob,
                        size_t blob_size,
                        const MappingList &mappings,
                        bool skip_dump_if_principal_mapping_not_referenced,
                        uintptr_t address_within_principal_mapping,
                        bool sanitize_stack,
                        const MicrodumpExtraInfo &microdump_extra_info) {
        LinuxPtraceDumper dumper(crashing_process);
        const ExceptionHandler::CrashContext *context = NULL;
        if (blob) {
            if (blob_size != sizeof(ExceptionHandler::CrashContext))
                return false;
            context = reinterpret_cast<const ExceptionHandler::CrashContext *>(blob);
            dumper.SetCrashInfoFromSigInfo(context->siginfo);
            dumper.set_crash_thread(context->tid);
        }
        MicrodumpWriter writer(context, mappings,
                               skip_dump_if_principal_mapping_not_referenced,
                               address_within_principal_mapping, sanitize_stack,
                               microdump_extra_info, &dumper);
        if (!writer.Init())
            return false;
        writer.Dump();
        return true;
    }

}  // namespace google_breakpad
